package demo1;

class Solution {
    public void solve(char[][] board) {

        //===================利用两个for循环进行遍历=============================
        // 矩阵的行数
        int m = board.length;
        // 矩阵的列数
        int n = board[0].length;
        // 利用两个 for 循环，遍历矩阵中的一些特殊的单元格，将它们赋值为 N
        // 特殊的单元格：必然是从边界处开始的
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // i == 0：表示在第 0 行，处于边界位置
                // j == 0：表示在第 0 列，处于边界位置
                // i == (m - 1)：表示在最后一行，处于边界位置
                // j == (n - 1)：表示在最后一列，处于边界位置
                if (i == 0 || j == 0 || i == (m - 1) || j == (n - 1)) {
                    // 从这些单元格开始向腹部延伸下去，找到所有和边界单元格想通的那些 O
                    dfs(board, i, j);
                }
            }
        }

        // 第二个 for 循环，开始修改
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // board[i][j] == 'O' 表示无法从边界格子中延伸过来
                // 表示被 'X' 围绕的区域
                if (board[i][j] == 'O') {
                    // 修改为 X
                    board[i][j] = 'X';
                }
                // board[i][j] == 'N' 表示是从边界格子中延伸过来
                if (board[i][j] == 'N') {
                    // 修改为 O
                    board[i][j] = 'O';
                }
            }
        }
    }

    //===================深度优先搜索=============================
    //1.处理边界
    //2.进行修改/处理
    //3.向四个方向进行搜索
    public void dfs(char[][] board, int i, int j) {
        // dfs搜索、递归终止条件
        // i < 0 ，越界
        // j < 0 ，越界
        // i >= board.length ，越界
        // j >= board[0].length ，越界
        // board[i][j] == X ，不需要继续搜索下去
        // board[i][j] == N ，这个格子已经被访问过，不需要继续搜索下去
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == 'N') {
            return;
        }
        // 否则说明当前单元格是 O，最后需要保留下来的那种
        // 将当前单元格置为 N ，避免其它格子 dfs 过程中又把它加入到计算中
        board[i][j] = 'N';
        // 在当前单元格的四个方向开始搜索
        // 上：（ 0 ， -1 ）
        // 下：（ 0 ， 1 ）
        // 左：（ -1 ， 0 ）
        // 右：（ 1 ， 0 ）
        // dx 为行的方向数组
        int dx[] = {-1, 1, 0, 0};
        // dy 为行的方向数组
        int dy[] = {0, 0, -1, 1};
        // 朝着这四个方向开始延伸搜索下去
        for (int index = 0; index < 4; index++) {
            // 下一个即将去搜索网格的横坐标
            int next_i = i + dx[index];
            // 下一个即将去搜索网格的纵坐标
            int next_j = j + dy[index];
            // 继续搜索
            dfs(board, next_i, next_j);
        }
    }
}